package com.cdream.basic.algorithm.leetcode.findElement;

/**
 * @author cdream
 * @date 7/16/21
 */
public class Offer53 {
    public static void main(String[] args) {
        int search = new Offer53().search(new int[]{5, 7, 7, 8, 8, 10}, 10);
    }

    public int search(int[] nums, int target) {
        if (nums.length == 0) {
            return 0;
        }
        int index = findOneIndex(nums, target);
        if (index == -1 || nums[index] != target) {
            return 0;
        }
        int count = 1;
        for (int i = index - 1; i >= 0; i--) {
            if (nums[i] != target) {
                break;
            }
            count++;
        }
        for (int i = index + 1; i < nums.length; i++) {
            if (nums[i] != target) {
                break;
            }
            count++;
        }
        return count;
    }

    public int findOneIndex(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;
        while (end >= start) {
            int mid = start + (end - start) / 2;

            if (nums[mid] > target) {
                end = mid - 1;
            } else if (nums[mid] < target) {
                start = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
}